package 面试今典150;

public class 今典5_169多数元素 {
    public int majorityElement(int[] nums) {
        /*
        思路1：摩尔投票
        初始候选人num[0] 票数count = 1
        如果有和nums[0] 相同的元素 ,count ++,否则count --；
        当前count = 0，更换候选人
         */
        return moer(nums);
    }
    public int moer(int[] arr){
        int x = arr[0];
        int count = 0;
        for(int val : arr){
            if (count > 0 ){
                count = val == x ? ++count : --count;
            }else {
                x = val;
                count = 1;
            }
        }
        return x;
    }

    public static void main(String[] args) {
        new 今典5_169多数元素().majorityElement(new int[]{1,1,2});
    }
}
